package 力扣_排序算法.归并;

/**
 * @author zx
 * @create 2022-08-30 15:30
 */
public class 数组中的逆序对 {
    public int reversePairs(int[] nums) {
        return mergeInternal(nums,0,nums.length - 1);
    }
    //传入一个数组arr,就可以求出在arr[l,r]上的逆序对的个数
    private int mergeInternal(int[] arr,int l,int r){
        if(l >= r){
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        //先求出左区间的逆序对的个数
        int left = mergeInternal(arr,l,mid);
        //再求出右区间的逆序对的个数
        int right = mergeInternal(arr,mid + 1,r);
        //排好序的左右子区间还存在逆序
        if(arr[mid] > arr[mid + 1]){
            return merge(arr,l,mid,r) + left + right;
        }else{
            // 左右区间已经有序，整个集合也有序
            return left + right;
        }
    }
    //合并arr两个有序区间[l,mid],[mid + 1,r],返回合并过程中逆序对的个数
    private int merge(int[] arr, int l, int mid, int r) {
        int[] temp = new int[r - l + 1];
        int res = 0;
        for(int i = 0;i < temp.length;i++){
            temp[i] = arr[i + l];
        }
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左区间已经合并完毕，放入右区间元素
                arr[k] = temp[j - l];
                j ++;
            }else if (j > r) {
                // 右区间已经合并完毕，放入左区间元素
                arr[k] = temp[i - l];
                i ++;
            }else if (temp[i - l] <= temp[j - l]) {
                // 左区间的元素 < 右区间元素，不构成逆序对
                arr[k] = temp[i - l];
                i ++;
            }else {
                // 右区间的元素 < 左区间的元素，构成逆序对
                // 此时逆序对的个数 = mid - i + 1
                res += (mid - i) + 1;
                arr[k] = temp[j - l];
                j ++;
            }
        }
        return res;
    }
}
